﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Collections.ObjectModel;
using Engine.Dtd.Schema;
using Engine.Sgml.Matching;
using Engine.Sgml.Validation;

namespace Engine.Sgml.Merging {
    internal sealed class MatchMerger {
        private AnyOrderCaptureAllocator anyOrderCaptureAllocator = new AnyOrderCaptureAllocator();
        private OnlyOneCaptureAllocator onlyOneCaptureAllocator = new OnlyOneCaptureAllocator();
        private SequenceCaptureAllocator sequenceCaptureAllocator = new SequenceCaptureAllocator();
        private IList<Match> matches = new List<Match>();
        private InconsistentBlockExtractor blockExtractor = new InconsistentBlockExtractor();

        public IList<InconsistentBlock> Merge(IList<Capture> captures) {
            Guard.ArgumentNotNull(captures, "captures");
            Debug.Assert(captures.Count > 0);
            Debug.Assert(captures.Any(c => c.Entity.IsModelMatch));

            matches = GetMatchCollection(captures);
            if (matches.Count == 0) {
                Match first = GetFirstMatch(captures);
                return blockExtractor.Extract(captures, first);
                }
            Debug.Assert(matches.All(m => matches[0].Model == m.Model));

            if (matches[0].Model.CanRecur()) {
                for (int i = 1, j = 2; j < matches.Count; j++) {
                    do {
                        if (matches[j].Type == AccordanceTypes.Partial) {
                            Merge(matches[i], matches[j]);
                            if (matches[j].Type == AccordanceTypes.Partial) {
                                for (int k = i - 1; k > 0; k--) {
                                    Merge(matches[k], matches[j]);
                                    if (matches[j].Type != AccordanceTypes.Partial)
                                        break;
                                    }
                                }
                            i = j;
                            break;
                            }
                        j++;
                        } while (j < matches.Count);
                    if (matches[i].Type == AccordanceTypes.Full)
                        i++;
                    }
                if (matches.Count > 1 && matches[1].Type == AccordanceTypes.Partial)
                    Merge(matches[0], matches[1]);
                }
            else {
                for (int i = 1; i < matches.Count; i++) {
                    Merge(matches[0], matches[i]);
                    }
                }
            Debug.Assert(matches.Count > 0);
            Debug.Assert(matches.All(m => MatchTestUtility.Verify(m)));
            RemoveIllegalCaptures(matches);
            Match firstMatch = matches[0];
            matches.Clear();
            return blockExtractor.Extract(captures, firstMatch);
            }

        private void Merge(Match first, Match second) {
            Debug.Assert(first != null && second != null);
            Debug.Assert(first.Model == second.Model);

            ICaptureAllocator allocator = GetAllocator(first.Model);
            int firstCaptureIndex = -1;
            for (int secondCaptureIndex = 0; secondCaptureIndex < second.Captures.Count; secondCaptureIndex++) {
                Capture secondCapture = second.Captures[secondCaptureIndex];
                if (secondCapture.Success) {
                    // Insert an inclusion element
                    if (secondCapture.Entity.IsInclusion) {
                        allocator.Insert(first, ref secondCapture, ref firstCaptureIndex);
                        second.Captures.RemoveAt(secondCaptureIndex--);
                        continue;
                        }
                    // Find capture
                    Match container;
                    int index = FindCaptureIndex(first, first.Captures.Count - 1, secondCapture.Entity.Model, out container);
                    if (index < 0) {
                        if (allocator.Add(first, ref secondCapture))
                            second.Captures.RemoveAt(secondCaptureIndex--);
                        }
                    else {
                        firstCaptureIndex = index;
                        if (first == container)
                            AllocateCapture(first, second, allocator, ref firstCaptureIndex, ref secondCaptureIndex, ref secondCapture);
                        else {
                            int prevIndex = secondCaptureIndex;
                            AllocateCapture(container, second, allocator, ref firstCaptureIndex, ref secondCaptureIndex, ref secondCapture);
                            while (prevIndex == secondCaptureIndex && second.Captures[secondCaptureIndex].Success) {
                                index = FindCaptureIndex(first, --firstCaptureIndex, secondCapture.Entity.Model, out container);
                                if (index < 0) {
                                    if (allocator.Add(first, ref secondCapture))
                                        second.Captures.RemoveAt(secondCaptureIndex--);
                                    break;
                                    }
                                else {
                                    firstCaptureIndex = index;
                                    prevIndex = secondCaptureIndex;
                                    AllocateCapture(container, second, allocator, ref firstCaptureIndex, ref secondCaptureIndex, ref secondCapture);
                                    }
                                }
                            }
                        }
                    }
                else if (secondCapture.Entity.IsIllegalElement && !HasSuccessCaptureBefore(second, secondCaptureIndex)) {
                    int index = -1;
                    allocator.Insert(first, ref secondCapture, ref index);
                    second.Captures.RemoveAt(secondCaptureIndex--);
                    }
                Debug.Assert(MatchTestUtility.Verify(first));
                Debug.Assert(MatchTestUtility.Verify(second));
                }
            }

        private int FindCaptureIndex(Match match, int startCaptureIndex, IModelGroupsNode model, out Match container) {
            container = null;
            for (int i = startCaptureIndex; i >= 0; i--) {
                Capture c = match.Captures[i];
                IModelGroupsNode item = c.Entity.Model;
                if (item == null)
                    continue;
                if (EqualModelGroupItems(model, item)) {
                    container = match;
                    return i;
                    }
                if (c.Entity.IsModelMatch) {
                    Match inner = c.Entity.Match;
                    int j = FindCaptureIndex(inner, inner.Captures.Count - 1, model, out container);
                    if (j > 0)
                        return j;
                    }
                }
            return -1;
            }

        private static bool EqualModelGroupItems(IModelGroupsNode first, IModelGroupsNode second) {
            if (second.IsModelGroups() || second == InclusionNode.Instance)
                return second == first;
            else
                return second.Name == first.Name;
            }

        private void AllocateCapture(Match first, Match second, ICaptureAllocator allocator, ref int firstCaptureIndex, ref int secondCaptureIndex, ref Capture secondCapture) {
            Capture firstCapture = first.Captures[firstCaptureIndex];
            if (firstCapture.Success) {
                if (firstCapture.Entity.IsModelMatch) {
                    CaptureEntity entity = secondCapture.Entity;
                    Debug.Assert(entity.IsModelMatch, "The second capture does not contain model match object.");
                    // Merge two model groups
                    if (entity.Model.CanRecur()) {
                        // If at least one model has partial accordance
                        if (entity.Match.Type == AccordanceTypes.Partial || firstCapture.Entity.Match.Type == AccordanceTypes.Partial) {
                            Merge(firstCapture.Entity.Match, entity.Match);
                            if (entity.Match.Captures.Any(c => c.Success) && !Merge(entity.Match, first.Captures, firstCaptureIndex)) {
                                allocator.Insert(first, ref secondCapture, ref firstCaptureIndex);
                                second.Captures.RemoveAt(secondCaptureIndex--);
                                }
                            else if (entity.Match.Captures.Count > 0)
                                second.Captures[secondCaptureIndex] = new Capture(entity.Match, false);
                            else
                                second.Captures.RemoveAt(secondCaptureIndex--);
                            }
                        else {
                            allocator.Insert(first, ref secondCapture, ref firstCaptureIndex);
                            second.Captures.RemoveAt(secondCaptureIndex--);
                            }
                        }
                    else {
                        Merge(firstCapture.Entity.Match, entity.Match);
                        if (entity.Match.Captures.Count == 0 || !entity.Match.Captures.Any(c => c.Success))
                            second.Captures.RemoveAt(secondCaptureIndex--);
                        }
                    }
                else if (firstCapture.Entity.Model.CanRecur()) {
                    allocator.Insert(first, ref secondCapture, ref firstCaptureIndex);
                    second.Captures[secondCaptureIndex] = new Capture(secondCapture.Entity.Model);
                    for (int j = secondCaptureIndex + 1; j < second.Captures.Count; j++) {
                        secondCapture = second.Captures[j];
                        if (firstCapture.Entity.Model == secondCapture.Entity.Model || secondCapture.Entity.IsInclusion || secondCapture.Entity.IsIllegalElement) {
                            allocator.Insert(first, ref secondCapture, ref firstCaptureIndex);
                            second.Captures.RemoveAt(j--);
                            }
                        else
                            break;
                        }
                    }
                }
            else {
                allocator.Replace(first, ref secondCapture, firstCaptureIndex);
                second.Captures[secondCaptureIndex] = new Capture(secondCapture.Entity.Model);
                }
            }

        private bool Merge(Match match, CaptureCollection captures, int startIndex) {
            Debug.Assert(startIndex < captures.Count && startIndex >= 0);
            int index = startIndex;
            while (--index >= 0) {
                CaptureEntity entity = captures[index].Entity;
                if (entity.Model == match.Model) {
                    Merge(entity.Match, match);
                    if (match.Captures.Count == 0 || !match.Captures.Any(c => c.Success))
                        return true;
                    }
                else if (entity.IsIllegalElement || entity.IsInclusion)
                    continue;
                else
                    return false;
                }
            return false;
            }

        private ICaptureAllocator GetAllocator(DModelGroups model) {
            ICaptureAllocator allocator = null;
            switch (model.OrderType) {
                case DGroupOrderType.OnlyOne:
                    allocator = onlyOneCaptureAllocator;
                    break;
                case DGroupOrderType.Sequence:
                    allocator = sequenceCaptureAllocator;
                    break;
                case DGroupOrderType.AnyOrder:
                    allocator = anyOrderCaptureAllocator;
                    break;
                default:
                    throw new InvalidOperationException("Unknown the order type of the DModelGroups object.");
                }
            return allocator;
            }

        private bool HasSuccessCaptureBefore(Match match, int index) {
            for (int i = 0; i < index; i++) {
                if (match.Captures[i].Success)
                    return true;
                }
            return false;
            }

        private IList<Match> GetMatchCollection(IList<Capture> captures) {
            matches.Clear();
            for (int i = 0; i < captures.Count; i++) {
                CaptureEntity entity = captures[i].Entity;
                if (entity.IsModelMatch) {
                    if (entity.Match.Type != AccordanceTypes.Inconsistent)
                        matches.Add(entity.Match);
                    }
                else if (entity.IsIllegalElement) {
                    if (matches.Count != 0)
                        matches[matches.Count - 1].Captures.Add(captures[i]);
                    }
                else
                    throw new InvalidOperationException();
                }
            return matches;
            }

        private static Match GetFirstMatch(IList<Capture> captures) {
            for (int i = 0; i < captures.Count; i++) {
                CaptureEntity entity = captures[i].Entity;
                if (entity.IsModelMatch)
                    return entity.Match;
                }
            throw new InvalidOperationException();
            }

        private static void RemoveIllegalCaptures(IList<Match> matches) {
            Debug.Assert(matches.Count > 0);
            Match match = matches[0];
            for (int i = 0; i < matches.Count; i++) {
                if (matches[i].Captures.Count > 0) {
                    RemoveIllegalCaptures(matches[i]);
                    }
                }
            }

        private static void RemoveIllegalCaptures(Match match) {
            Debug.Assert(match != null);
            Debug.Assert(match.Captures.Count > 0);
            int index = match.Captures.Count - 1;
            do {
                int inclusionIndex = index;
                if (inclusionIndex >= 0 && match.Captures[inclusionIndex].Entity.IsInclusion) {
                    inclusionIndex--;
                    while (inclusionIndex >= 0 && match.Captures[inclusionIndex].Entity.IsInclusion) {
                        inclusionIndex--;
                        }
                    }
                if (inclusionIndex >= 0 && match.Captures[inclusionIndex].Entity.IsIllegalElement) {
                    index = --inclusionIndex;
                    while (index >= 0 && match.Captures[index].Entity.IsIllegalElement) {
                        index--;
                        }
                    }
                else
                    break;
                } while (true);
            index++;
            if (index < match.Captures.Count && match.Captures[index].Entity.IsIllegalElement) {
                do {
                    match.Captures.RemoveAt(index);
                    } while (match.Captures.Count != index);
                }
            }
        }
    }